#include <mpi.h>
#include <stdio.h>
#include <unistd.h>

int main(int argc, char** argv){
    int rank, nproc;
    int TAG = 100;
    MPI_Request send_request, recv_request;
    MPI_Status send_status, recv_status;
    MPI_Init(&argc, &argv);
    MPI_Comm_size(MPI_COMM_WORLD, &nproc);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    int data = rank+1;
    printf("Proc#%d:\tdata=%d\n",rank,data);
    int nproc_lg2;
    for (nproc_lg2 = 0; nproc_lg2<32; nproc_lg2++){
        if ((1<<nproc_lg2) == nproc){
            break;
        }
    }
    if ((1<<nproc_lg2)!=nproc){
        if (rank==0){
            printf("The number of procs is not the power of 2. Exit.\n");
        }
        goto over;
    }

    for (int height = 0; height<nproc_lg2; height++){
        int peer = ((1<<height)^rank);
        if (peer>rank){
            MPI_Send(&data,1,MPI_INT,peer,TAG,MPI_COMM_WORLD);
            MPI_Recv(&data,1,MPI_INT,peer,TAG,MPI_COMM_WORLD,&recv_status);
        }
        else{
            int temp;
            MPI_Recv(&temp,1,MPI_INT,peer,TAG,MPI_COMM_WORLD,&recv_status);
            data+=temp;
            MPI_Send(&data,1,MPI_INT,peer,TAG,MPI_COMM_WORLD);
        }
        MPI_Barrier(MPI_COMM_WORLD);
    }
    printf("Proc#%d:\tsum_of_data=%d\n",rank,data);



over:
    MPI_Finalize();
}